# 动态规划需要定义一个子问题
# 子问题是和原问题相似，但是规模较小


class Solution:

    def rob(self, nums):
        
        N = len(nums) # 房子的数量
        
        dp = [0] * (N + 1) # 使用数组的形式存储

        dp[0] = 0
        dp[1] = nums[0]
        
        for k in range(2, N + 1):
            # 注意这里数组是默认少一位
            dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])

        return dp[N]



    


    # def rob(self, nums: List[int]) -> int:
    #     n = len(nums) - 1

    #     def rob_k(k):
    #         if k < 0:
    #             return 0
    #         if k == 0 :
    #             return nums[0]
            
    #         # if k == 1:
    #         #     return max(nums[0], nums[1])
            
    #         cost = max(nums[k]+rob_k(k-2), nums[k-1]+rob_k(k-3))
    #         return cost
        
    #     return rob_k(n)

    
    

if __name__ == '__main__':

    a = [2,7,9,3,1]
    sol = Solution()
    res = sol.rob(a)
    print(res)




